The invention relates generally to redundant arrays. In particular, the invention relates to a method for deciding which failed points in the array should be corrected by a redundant row and which should be corrected by a redundant column.
In many large integrated circuits having a regular structure, such as memory chips, it has become common practice to provide redundant memory locations to correct for memory locations which have failed. In one dimensional redundancy, the redundancy extends in one direction only. For instance, if a chip is divided into rows and column, then memory locations are associated with each intersection of a row or column. Usually there is some structure associated with both the rows and columns themselves, such as word lines running along the direction of the row or a sense amplifier reading any memory element along a particular column. In one dimensional redundancy, extra rows are provided or extra columns are provided. For example, if extra columns are provided, then whatever column contains a faulty memory location is replaced by a redundant column. Once the replacement has been effected, all memory locations logically located in the faulty column are relocated in a redundant column. Thus many faultless memory locations are likely to be replaced in order to correct one failed memory location. The redundant column also includes much of the additional circuitry associated with the column. Of course, there is a fixed number of redundant columns so that, if errors are found in an excessive number of columns, the redundant columns become insufficient to correct the errors, and the chip must be rejected.
An alternative approach is two dimensional redundancy in which both redundant rows and columns are provided. This approach is particularly useful since some errors are associated with the entire row and other errors are associated with the entire column, or at least large parts thereof. For instance, a completely failed sense amplifier would incapacitate the entire row, and it is efficient to replace the failed memory locations with a single redundant row rather than using multiple redundant columns to replace all columns intersecting that row. It should be mentioned that the redundant replacement is done automatically and relies on a simple test of every memory location in the memory chip. A bit failure map is then generated which indicates which locations or bits have failed and thus need replacing.
Sometimes, however, the choice of choosing either row replacement or column replacement is not so straightforward. Some failure mechanisms will present the situation where the number of failures in one or both dimensions exceeds the number of available word lines or bit lines. In these situations, the selection must take advantage of both the redundant word lines and bit lines, but which combination of the two sets of lines is not always apparent, particularly when the selection must be done by automated equipment.
There is presented in FIG. 1 an example of a memory chip which has a 20.times.20 memory array, that is 400 memory locations or bits. A total of 20 original bit lines 10 extend horizontally and are numbered in hexadecimal notation from 0 to 13. A total of twenty original word lines 12 extend vertically and are likewise numbered in hexadecimal. It is, of course, not untypical for a memory chip to be much larger but the example of FIG. 1 is sufficient to explain the invention. Also included in the chip of FIG. 1 are four redundant word lines 14 and two redundant bit lines 16. At each intersection of a word line 12 or 14 and a bit line 10 or 16 is a memory element.
In the final stages of manufacturing a memory chip, a testing program tests each of the 400 memory elements at the intersections of the original bit and word lines 10 and 12 and stores the results of the testing in a bit failure map. For sake of simplicity, a sample bit failure map is superimposed on FIG. 1 to show a configuration of failed bits 18 associated with the original bit and word lines 10 and 12 for those failed bits 18. The purpose of the redundancy is to replace either the bit line 10 or the word line 12 associated with each failed bit 18. The replacement is made with the redundant bit lines 16 and word lines 14. However, the choice of using a redundant bit line 16 or a redundant word line 14 for a particular failed bit 18 may be difficult. There are 5 word lines 12 which have 2 fails each and 1 word line which has 1 fail. Several simple but reasonable algorithms fail to correct the bit errors indicated in FIG. 1 with the four redundant word lines 14 and two redundant bit lines 16. If the selected algorithm selects any four out of the 5 word lines which have 2 fails as word lines to repair, this device appears to be a reject since the two redundant bit lines 16 cannot correct the remaining failures. There are only two combinations of replacement assignments which will correct the bit errors of FIG. 1. The first combination is replacing the word lines 12 numbered 6, 8, A and B with the four redundant word lines 14 and replacing the bit lines 10 numbered 4 and 6 with the two redundant bit lines 16. The second combination replaces the word lines 12 numbered 7, 8, 9 and B and the bit lines numbered 3 and 7. No other combination works.
Thus the difficulty exists of developing a method which will select the proper combination of redundant rows and columns, or bit lines and word lines in the case of a memory chip, which will correct the failed elements or bits, if such correction is possible. The process must account for a generalized arrangement of failed bits 18 within the original array.
The inventors are aware of several commercially available redundancy algorithms, either in hardware or software implementations. There are two hardware implementations, the Memory Repair Analyzer available from Teradyne, Inc. of Woodland Hills, Calif. and the High Speed Redundancy Processor available from Eaton Corp. also of Woodland Hills, Calif. There are five software implementations available from Fairchild Camera and Instrument Corp. of Simi Valley, Calif., from Pacific Western Systems, Inc. of Mountain View, Calif., from Megatest Corp. of San Jose, Calif., from Tektronix, Inc. of Portland, Oreg., and the Failed Image Processing System from Accutest Corp. of Chelmsford, Mass.
Furthermore, Hayasaka et al have described both a system and an algorithm for repairing a dual dimensional redundant array in a technical article entitled "Testing System for Redundant Memory", appearing in 1982 IEEE Test Conference at pages 240-243. An interesting aspect of this paper is that they determine unrepairable conditions for the arrangement of failures before attempting to repair the chip.